"""lc46,Permutations. using backtracking method."""
from copy import deepcopy
from typing import List


class Solution:
    def __init__(self):
        self.ans = []

    def permute(self, nums: List) -> List[List]:
        """permute.

        Return all possible arrangements of nums.

        Args:
            nums (List): nums

        Returns:
            List[List]:
        """
        self._backtracking(nums, level=0)
        return self.ans

    def _backtracking(self, nums, level):
        """_backtracking.

        Args:
            nums:
            level:
        """
        if level == len(nums) - 1:
            # use deepcopy, it works.
            self.ans.append(deepcopy(nums))
            return

        for i in range(level, len(nums)):
            nums[i], nums[level] = nums[level], nums[i]
            self._backtracking(nums, level + 1)
            nums[i], nums[level] = nums[level], nums[i]


if __name__ == "__main__":
    nums = [1, 2, 3]
    a = Solution()
    print(a.permute(nums))
